//
// Created by Administrator on 2023/10/12.
// 素数,埃氏筛法
/*
 * 讲解 https://zhuanlan.zhihu.com/p/146418699
 * https://blog.csdn.net/GD_ONE/article/details/104660294
 *
 * https://oj.hterobot.com/?#/question/107719?order=ID&offset=0&limit=20&teamid&name=%E7%B4%A0%E6%95%B0&range=public
 * 21个测试用例:11个通过10个超时
 * 
 * https://www.luogu.com.cn/problem/P3912
 * 10个测试用例:9个通过1个超时/
 * int, long long都一样
*/

#include <iostream>
using namespace std;

int main()
{
    long long count=0;
    long long n=100;
    n = 1740948; // out: 130971
//    n= 2115790; //out:156902
//    n=91571465;// out: 5302853
//    n = 65090061389;//out: 2728793966
//    cin>>n;
    bool isPrime[n+1]={0};
    for (long long i = 2; i < n+1; ++i)
        isPrime[i]=true;
    for (long long j = 2; j < n+1 ; ++j)
    {
        if(isPrime[j])
        {
            for (long long k = j*2; k < n+1; k+=j)
            {
                isPrime[k]=false;
            }
        }
        if(isPrime[j])
            ++count;
    }
    cout<<count;
//    cout<<n-3;
    return 0;
}
